// https://www.luogu.com.cn/problem/P1757
#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
const int inf = 0x3f3f3f3f;
#define rf(i, n) for (int i = 1; i <= (n); ++i)
#define MAX_SIZE 100
#define MAXN 1005

int m, n, x;

vector<int> v[MAXN], w[MAXN];
int f[MAXN];

int main() {
    scanf("%d%d", &m, &x);
    rf(i, x) {
        int tw, tv, tx;
        scanf("%d%d%d", &tw, &tv, &tx);
        n = max(n, tx), v[tx].push_back(tv), w[tx].push_back(tw);
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = m; j >= 0; --j) {
            for (int k = 0, ed = v[i].size(); k < ed; ++k) {
                if (j >= w[i][k]) f[j] = max(f[j], f[j - w[i][k]] + v[i][k]);
            }
        }
    }
    int ans = 0;
    rf(j, m) ans = max(ans, f[j]);
    printf("%d", ans);
}
